⟸ Go Back ⟸

Exercise 5 (Homework 2).

(regular languages, reverse)

Reverse of a regular language is regular

1. Explicitly construct the minimum DFA for the language L^R, where

   1. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|_b\in 2\mathbb N )\}.
   2. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|_b\in 2\mathbb N +1)\}.
   3. L=\{w\in\{a,b\}^*\mid \forall w_1,w_2\ (w=w_1aw_2\Rightarrow |w_1|\in 2\mathbb N )\}.

   Construct the minimum DFA recognizing L. From that DFA, construct an NFA A recognizing the language L^R. Now, using the power-set construction, make A deterministic and then minimize the DFA obtained.

2. Given a DFA A as input, what is the cost of constructing a DFA for L(A)^R?

3. Reversing the direction of transitions and exchanging initial and final states in a DFA A gives an NFA B for L(A)^R. If the obtained NFA B is actually a DFA and A was minimum, is B minimum too?

4. An NFA is uniquely accepting if for every word there is a unique accepting execution. Show that, for a uniquely accepting NFA A, the NFA A^R is uniquely accepting.